package com.tucc.hello.leetcode.no401_800.no518;

import java.util.Arrays;

/**
 * @author tucc
 * @description todo
 * @package com.tucc.hello.leetcode
 * @date 2021/5/20
 **/
public class Solution {

    public static void main(String[] args) {
        Solution solution = new Solution();
        int amount = 500;
        int[] coins = {3, 5, 7, 8, 9, 10, 11};
        System.out.println(solution.change(amount, coins));
        System.out.println(solution.change2(amount, coins));
    }


    public int change(int amount, int[] coins) {
        int[] dp = new int[amount + 1];
        dp[0] = 1;

        for (int coin : coins) {
            for (int j = coin; j <= amount; j++) {
                dp[j] = dp[j] + dp[j - coin];
            }
        }
        return dp[amount];
    }

    public int change2(int amount, int[] coins) {
        Arrays.sort(coins);
        change(amount, coins, 0, 0);
        return count;
    }

    public int count = 0;


    public void change(int amount, int[] coins, int curCoin, int curSum) {
        if (curCoin < coins.length && curSum < amount) {
            int nextSum = curSum + coins[curCoin];
            if (nextSum == amount) {
                count++;
            } else if (nextSum < amount) {
                change(amount, coins, curCoin, nextSum);
                if (curCoin + 1 < coins.length) {
                    nextSum = curSum + coins[curCoin + 1];
                    if (nextSum == amount) {
                        count++;
                    } else if (nextSum < amount) {
                        change(amount, coins, curCoin + 1, curSum);
                    }
                }
            }
        }
    }
}
